# 路线图
# 假设：a,b,c,d,e,f,g,h,k,k,l,m 这13个点的代号为0，1，2，3，4，5，6，7，8，9，10,11,12
eulerEdges = [
    (0, 2),(0, 1),(0, 3),(0, 4),(1, 2),
    (1, 3),(1, 5),(6, 2),(3, 5),(4, 5),
    (4, 7),(4 ,10),(5, 6),(5, 8),(5, 11),
    (6, 9),(6, 12),(7, 10),(7, 11),(8, 9),
    (8, 11),(9, 11),(9, 12),(10, 11),(11, 12)
]#  这个列表里的25个元素均代表一条路径
# 可以通过修改start的值来确定起始位置
start = 3    # 检查员起始位置，笔者认为从效率考虑，应该从d点开始检查
visited = [0 for i in range(len(eulerEdges))] #访问过的路
queue = [] # 保存路径信息
# print(queue)
eulerFlag = False

def isEuler():
    allVisited = True
    for e in visited:
        if e == 0:
            allVisited = False
    if allVisited:
        if queue[0] == queue[len(queue) - 1]:
            return 1
        else:
            return 2
    return 0

def printPath(flag):
    if flag == 1:
        print("是欧拉回路:", end="")
    else:
        print("是欧拉道路:", end="")
    for i in range(len(queue)):
        if i < len(queue) - 1:
            print(queue[i], "-> ", end="")
        else:
            print(queue[i])

# 搜索过程只保存一条路的状态的信息，且不重复经过某一路线
def dfs(u):
    li = queue.append(u)
    flag = isEuler()  # 判断当前路径是不是欧拉路，如果是则打印
    if flag > 0:
        eulerFlag = True
        printPath(flag)
    for i in range(len(eulerEdges)):
        if visited[i] == 1:
            continue
        edge = eulerEdges[i]
        if edge[0] == u:
            visited[i] = 1
            dfs(edge[1])
            #queue.pop()     # 将搜索过的点弹出队列
            # visited[i] = 0  # 重置访问状态
        elif edge[1] == u:
            visited[i] = 1
            dfs(edge[0])
            #queue.pop()     # 将搜索过的点弹出队列
            # visited[i] = 0  # 重置访问状态
dfs(start)
# if not eulerFlag:  # 判断另一种情况
#     print("否则：不是欧拉回路或欧拉道路")
